package algorithm_optimal_solution.StackAndQueue;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

//递归实现汉诺塔，左移右其实是循环的5步，可以用2个塔来代入模拟。
public class RecursiveForHanoi {

    public int recursive(int count,String left,String mid,String right,String from,String to){
        if(count==1){
            if(from.equals("mid") || to.equals("mid")){
                System.out.println("Move 1 from " + from + " to " + to);
                return 1;
            }else{
                System.out.println("Move 1 from " + from + " to " + mid);
                System.out.println("Move 1 from " + mid + " to " + to);
                return 2;
            }
        }else{
            if(from.equals("mid") || to.equals("mid")){
                String another=from.equals("left") || to.equals("left") ? "right" : "left";
                int part1=recursive(count-1,left,mid,right,from,another);
                System.out.println("Move " + count + " from " + from + " to " + to);
                int part2=1;
                int part3=recursive(count-1,left,mid,right,another,to);
                return part1+part2+part3;
            }else{
                int part1=recursive(count-1,left,mid,right,from,to);
                System.out.println("Move " + count + " from " + from + " to " + mid);
                int part2=1;
                int part3=recursive(count-1,left,mid,right,to,from);
                System.out.println("Move " + count + " from " + mid + " to " + to);
                int part4=1;
                int part5=recursive(count-1,left,mid,right,from,to);
                return part1+part2+part3+part4+part5;
            }
        }
    }

    public static void main(String[] args)throws IOException {
        BufferedReader scanner = new BufferedReader(new InputStreamReader(System.in));
        int len=Integer.parseInt(scanner.readLine());
        RecursiveForHanoi main = new RecursiveForHanoi();
        int steps = main.recursive(len,"left","mid","right","left","mid");
        System.out.println("It will move " + steps + " steps.");
    }

}
